// https://leetcode.cn/problems/happy-number/description/

// 算法思路总结：
// 1. 使用快慢指针法检测循环（Floyd判圈算法）
// 2. 慢指针每次计算一次平方和
// 3. 快指针每次计算两次平方和
// 4. 当快慢指针相遇时判断是否为1
// 5. 时间复杂度：O(logn)，空间复杂度：O(1)

#include <iostream>
using namespace std;

class Solution 
{
public:
    int digitSquareSum(int num)
    {
        int sum = 0;
        while (num)
        {
            int digit = num % 10;
            sum += digit * digit;
            num /= 10;
        }
        return sum;
    }

    bool isHappy(int n) 
    {
        int slow = n, fast = digitSquareSum(n);

        while (slow != fast)
        {
            slow = digitSquareSum(slow);
            fast = digitSquareSum(digitSquareSum(fast));
        }
        return slow == 1;
    }
};

int main()
{
    int n1 = 19, n2 = 2;

    Solution sol;
    cout << sol.isHappy(n1) << endl;
    cout << sol.isHappy(n2) << endl;

    return 0;
}